ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/newsgrp/group01b.txt/000053_icon-group-sender_Wed Mar 7 16:27:05 2001.msg

Internet Message Format | 2002-01-03 | 12KB

Return-Path: <icon-group-sender>
Received: (from root@localhost)
    by baskerville.CS.Arizona.EDU (8.11.1/8.11.1) id f27NQsQ29271
    for icon-group-addresses; Wed, 7 Mar 2001 16:26:54 -0700 (MST)
Message-Id: <[e-mail]>
Date: Wed, 07 Mar 2001 15:17:25 -0600
From: [e-mail]
Subject: Re: New Scientist puzzle
To: [e-mail]
Errors-To: [e-mail]
Status: RO
Content-Length: 10857

> It is interesting to look at the solution strategies followed. Unfortunately
I can't read (most) of them... It would be nice if there were explanations of
the diverse approaches for non-multilinguists to read.

> For instance, APL has a 5 line solution, but seems to use a monstrous
array on which it does pattern matching? I could (and would like to)
learn a great deal by implementing such strategies in other languages.

OK... a couple of days ago I posted a more detailed look at and explanation of
my SPITBOL solution to the SNOBOL4 list... I'll repost it here.  (It was a reply
to a post giving another alternative solution in generic SNOBOL4).

<---- Begin Forwarded Message ---->
Return-Path: <[e-mail]>
Date: Mon, 5 Mar 2001 02:00:51 -0600 (CST)
Reply-To: [e-mail]
From: [e-mail]
To: Multiple recipients of list <[e-mail]>
Subject: Re: New Scientist puzzle

>> Here, as promised, is my original solution in SPITBOL:
>
>
>      sq = 31
>      sqp1 = fence breakx("x") ("x" (len(1) $ n *notany(n) $ e
> +       *notany(n e) $ u *n) $ n2) $ xn2
> +     *?(sqs ? fence breakx("x") ("x" (*notany(n e u) $ v
> +       *notany(n e u v) $ i e *notany(n e u v i) $ r) $ n1) $ xn1
> +       *?(solbuf = solbuf "X" n1 xn2)
> +       *?($xn1 = $xn1 + 1) *?($xn2 = $xn2 + 1) fail)
>      lp = fence breakx("X") ("X" len(4) $ n1) $ xn1 ("x" len(4) $ n2) $ xn2
> +       *eq($xn1,1) *eq($xn2,1) *?(output = n1 "," n2) fail
> sqsfill    sqs = ((sqs "x" (((sq = sq + 1) le(sq,99)) * sq)),
> +     (sqs ? sqp1), (solbuf ? lp))            :s(sqsfill)
> end
>
> and the output from the last run:
>
> [quote]
>
> 6241,9409

> Not knowing anything about the spitbol extensions I find your solution hard
to follow.

Actually, it's pretty simple... there's only one goto and one label (other than
the END) in the whole program.

There are three SPITBOL extensions:

  1)  Embedded pattern match.   (subject ? pattern)  which returns (on success)
the portion of the subject matched by the pattern.  You can also use replacement
like any normal S*BOL pattern match, in which case the returned value is the
subject after the replacement (or maybe just the new value of the replaced
portion?  I'm not really sure as I'm writing this...)

  2)  Embedded assignment.  (subject = object)  which returns the value of the
subject.  This is very, very useful for creating side effects during a pattern
match (including generating debug output, for instance).

  3)  Alternative evaluation.  (expr1, expr2, expr3, ...)  which evaluates each
of the expressions in turn, and returns the value of the first one which
succeeds.  Subsequent expressions are not evaluated.

> Isn't it awfully complicated for such a simple problem?

Actually, no, it's really pretty simple.

One really nice thing about doing stuff like this is that you're able to use the
pattern matcher to do recursion and iteration, often without having to resort to
explicit labels and loop counters.

One of the things that I did in my solution was to precompute all the squares,
so that no multiplication (indeed, no arithmetic at all other than the tallying
the solutions) is necessary during the final portion of the program.  (Your
solution involves computing all the squares repeatedly for every qualifying
value of nn).

One of the other things I did was to prebuild the patterns, which is something
I'm relatively in the habit of doing even though the efficiency gain (in this
program at least) is certainly negligible, both because of all the unevaluated
expressions in the pattern, and since each of the patterns is only invoked ONE
time anyhow!  It does help clarify the program, though, because the structure of
the alternative evaluation expression at sqsfill is more apparent.

I qualified the "neun" term first, since that one has only three varying digits
and that (probably) truncates more of the possible solutions earlier in the
computation.

One thing which I did that apparently wasn't necessary was to make sure that the
indirection used an alpha character at the beginning of the name, thus following
normal variable naming conventions.  The fact that your solution works proves
that it isn't necessary to do that.

Also my solution drops potential candidates out of further consideration earlier
than yours does, since you break out solutions into all four of the component
characters even when the second one might already disqualify the candidate.

One minor problem with your solution is that if there WERE another solution pair
where both neun and vier values were unique. your program would only print the
first one.  It's pretty simple to fix that, though.

Your solution would run faster if you'd use *differ(a,b) instead of *ne(a,b)
since ne() forces each string [OK, character] to be converted to integer before
the comparison can be done.

In my programs, I tend to use stuff like FENCE BREAKX("X") "X" instead of just
"X" (which is running in unanchored mode) because I believe it's usually faster
to use BREAKX than it is to have the pattern matcher abandon the position and
step down the string to try again.  (Admittedly I haven't benchmarked that in
quite a long time).

Here's a running commentary...:

    sq = 31

Merely initalizes the loop counter.  Would sure like to have eliminated that,
but it would add more complexity elsewhere.

The following pattern is where most of the magic happens.  When it's running,
the string SQS consists of the four-digit squares, separated by "x" characters.

The pattern matches each of the four-digit squares in turn, starting at the
beginning of the string, and looks for one matching the "neun" rule.  When it
finds such, it then fires off an embedded pattern match, starting again at the
beginning of the list of squares, to find a square matching the "vier" rule.
If it finds a pair that work, it tacks them onto the end of the solution buffer
SOLBUF (in the form "Xvierxneun") and tallies the number of times each square is
used via indirection.  The "fail" forces the next vier to be found, if there is
one, and ultimately forces the embedded pattern match to fail, which forces the
outer pattern match to resume looking for another neun square.  Ultimately,
however, the sqp1 pattern is still doomed to fail because the embedded pattern
match looking for the vier term cannot succeed.  But that's okay, because
meanwhile it's built the solution buffer which contains all the candidate pairs.

>      sqp1 = fence breakx("x") ("x" (len(1) $ n *notany(n) $ e
> +       *notany(n e) $ u *n) $ n2) $ xn2
> +     *?(sqs ? fence breakx("x") ("x" (*notany(n e u) $ v
> +       *notany(n e u v) $ i e *notany(n e u v i) $ r) $ n1) $ xn1
> +       *?(solbuf = solbuf "X" n1 xn2)
> +       *?($xn1 = $xn1 + 1) *?($xn2 = $xn2 + 1) fail)

The next pattern processes the solution buffer.  It looks for each "X", then
four characters, then "x", four more characters.  Here I'm actually guilty of
the same thing I chastised you about;  I really should have moved the
*eq($xn1,1) before the matching of "x" etc, which would have allowed the matcher
to step to the next solution pair sooner.  Note that here I'm using the fact
that variable names are not case-sensitive (which I thought was really cute
while I was doing it, although now that I'm looking at it I'm wondering if
that's true when using indirection).  Anyhow, when it finds a solution pair of
squares which are both unique, it outputs the pair and then again hits a fail,
which forces the pattern matcher to try for another "X" and solution pair until
it reaches the end of the solution buffer... at which point it is, like pattern
sqp1, doomed to failure.

>      lp = fence breakx("X") ("X" len(4) $ n1) $ xn1 ("x" len(4) $ n2) $ xn2
> +       *eq($xn1,1) *eq($xn2,1) *?(output = n1 "," n2) fail

Now that the patterns are built, it mostly remains just to use them.  But first
we have to build the string sqs containing all the squares.  The following
statement uses an alternative evaluation expression... the first subexpression
succeeds for values of sq in the range to produce four-digit squares, appending
those to the string sqs separated by "x" characters.  The success of that
subexpression causes the GOTO to repeat the complete expression until the first
subexpression fails (after sq exceeds 99) at which point the next two
alternatives are tried in turn.  The first one finds all the solution pairs
using pattern sqp1 (as described above), builds the solbuf solution buffer, and
ultimately fails which forces the final subexpression to be tried.  That final
subexpression does a pattern match in the solution buffer to find and print all
solution pairs meeting the "both squares unique" rule.  Ultimately, it too fails
which causes the program to end.

> sqsfill    sqs = ((sqs "x" (((sq = sq + 1) le(sq,99)) * sq)),
> +     (sqs ? sqp1), (solbuf ? lp))            :s(sqsfill)
> end


> Here's mine in standard SNOBOL4:

[quote]

    &fullscan = 1
    nn = 31
AGAIN    nn = lt(nn, 99) nn + 1 :F(DONE)
    (nn * nn) len(1) $ v len(1) $ i len(1) $ e len(1) $ r fence
+        *ne(v, i) *ne(v, e) *ne(v, r) *ne(i, e) *ne(i, r) *ne(e, r)
+        :F(AGAIN)
    mm = 31
AGAIN2    mm = lt(mm, 99) mm + 1 :F(AGAIN)
    (mm * mm) len(1) $ n e len(1) $ u *n fence
+        *ne(n, v) *ne(n, i) *ne(n, e) *ne(n, r) *ne(n, u)
+        *ne(e, u) *ne(u, v) *ne(u, i) *ne(u, r)
+        :F(AGAIN2)
    $(v i e r) = $(v i e r) + 1
    $(n e u n) = $(n e u n) + 1
    result = result '|' v i e r ':' n e u n :(AGAIN2)
DONE    result '|' (len(4) $ vier ':' len(4) $ neun) . output
+        *eq($vier, 1) *eq($neun, 1)
END


maskull:Snobol>snobol4 test49.sno
The Macro Implementation of SNOBOL4 in C (C-MAINBOL) Version 0.99.4
    by Philip L. Budne, August 11, 1997
SNOBOL4 (Version 3.11, May 19, 1975)
    Bell Telephone Laboratories, Incorporated

No errors detected in source program

6241:9409
Normal termination at level 0
test49.sno:16: Last statement executed was 11

[end quote]

Certainly a reasonable solution, in any case!!  Not bad at all.

It's been interesting over on the Icon list to see how they've been handling
this one using Icon and MUMPS.  One of the fairly neat solutions observes that
they can use map() (like S*BOL's REPLACE()) to do all the testing in just two
operations... of course, those might be slower operations.  It would be
interesting to benchmark it both ways.  There has also been some use of
character set variables which neatly determines (for example) for the "vier"
term that all four digits are unique.



<----  End Forwarded Message  ---->

Gordon Peterson                  http://personal.terabites.com/
Support the Anti-SPAM Amendment!  Join at http://www.cauce.org/
12/19/98: Partisan Republicans scornfully ignore the voters they "represent".
12/09/00: the date the Republican Party took down democracy in America.